/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring
 */
class MinimumWindowSubstring {
    /**
     * 方法： minWindow
     * 逻辑: 使用滑动窗口技术找到包含字符串 t 的最小窗口子串
     * Args:
     *      s: 目标字符串
     *      t: 需要包含的子串
     * Returns:
     *      包含 t 的最小窗口子串，如果不存在则返回空字符串
     * Time:
     *      O(m+n) 或 O(m+n+∣Σ∣)，其中 m 为 s 的长度，n 为 t 的长度，
     *      ∣Σ∣=128。注意 left 只会增加不会减少，二重循环的时间复杂度为 O(m)。
     *      使用哈希表写法的时间复杂度为 O(m+n)，
     *      数组写法的时间复杂度为 O(m+n+∣Σ∣)。

     * Space:
     *      O(∣Σ∣)。无论 m 和 n 有多大，额外空间都不会超过 O(∣Σ∣)
     */
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if(sLen < tLen){
            return "";
        }
        char[] sCharArr = s.toCharArray();
        int[] cnt = new int[128];
        int less = 0;
        for(char c : t.toCharArray()){
            if(cnt[c] == 0){
                less++;
            }
            cnt[c]++;
        }
        int ansLeft = -1, ansRight = sLen;
        int left = 0;

        for(int right = 0; right < sLen; right++){
            char c = sCharArr[right];
            cnt[c]--;
            //窗口和子串t中的字母s数量一致了
            if(cnt[c] == 0){
                less--;
            }
            //覆盖子串
            while(less == 0){
                //更新最小子串位置
                if(right - left < ansRight - ansLeft){
                    ansRight = right;
                    ansLeft = left;
                }
                char leftC = sCharArr[left];
                if(cnt[leftC] == 0){
                    // leftC 移出窗口之前，检查出现次数，
                    // 如果窗口内 leftC 的出现次数和 t 一样，
                    // 那么 leftC 移出窗口后，窗口内 leftC 的出现次数比 t 的少
                    less++;
                }
                cnt[leftC]++; //左侧字母移出子串
                left++;
            }
        }
        return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
    }

    public static void main(String[] args) {
        MinimumWindowSubstring mws = new MinimumWindowSubstring();
        String s = "ADOBECODEBANCC";
        String t = "ABCC";
        String ans = mws.minWindow(s, t);
        System.out.println(ans);
    }

}